\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}

\usepackage{epstopdf}

\epstopdfDeclareGraphicsRule{.gif}{png}{.png}{%
  convert gif:#1 png:\OutputFile
}
\AppendGraphicsExtensions{.gif}


\begin{document}

\title{Minimum Weight Triangulation in 3-Dimension}
\author{Naresh Singh \and Anuj Goel}

\maketitle

\begin{abstract}
In this project, we implement various heuristics for computing Minimum Weight Triangulation in 3-Dimensional space. The weight of a triangulation of a set of points in the sum of the perimeters of the triangles in the triangulation. This is a known NP-Hard problem for points in 3 Dimensions. 
We have computed a Delaunay Triangulation of the given point set and reduced the total weight by removing edges.
\end{abstract}

\section{Our Approach}
We tried various approaches to solve this problem. They involved clustering and approaches like Greedy triangulation and Delaunay triangulation. Modification of Delaunay triangulation gave us the best results. In this report, we will detail our obervations with each of them. 
\\The main idea behind using clustering was to analyse distribution of points in 3D space and see if they form some clusters. We could run triangulation on individual clusters and merge them later. This idea would keep the cells in triangulation concentrated around those clusters. The triangulation achieved by this method had fewer edges and cells as compared to other approaces. However, the weight of the triangulation was still higher.
\\Then we computed the Triangulation using iterative method. We refer to it as Regular triangulation in the next sections.
\\We also played with greedy triangulation but its weight was higher than the previous approach.
\\Delaunay triangulation in 2D space maximizes minimum angle in the triangles. Delaunay Triangulation in 3D creates tetrahedrons whose circumsphere is empty. So, we triangulated given point set using Delaunay and observed that it gives minimum weight as compared to previous approaches. We used Delaunay triangulation as our starting point and modified it to minimize the weight further. This would give us a better result.
\\We implemented these algorithm in C++ using the \emph{CGAL} Library.

\section{Algorithm}
The algorithm starts with Delaunay triangulation of the given point set. Delaunay in 3D has an interesting flipping property. Its flip operations transform 2 tetrahedon into 3 tetrahedron and vice-versa. So, we realized, if we remove all 3-tetrahedrons from the triangulation it would still be valid. The modified triangulation contains lesser number of edges which reduces its weight.
\\We enumerated all the edges of the triangulation obtained using Delaunay. For every edge, we check if it has three neighboring cells. It means this edge is part of 3-tetrahedon and can be removed. The removal of edge would result in 2-tetrahedon reducing the weight by the length of removed edge. This also leaves the triangulation with one less cell. We keep removing edges until there exists any 3-tetrahedon in the triangulation.
\begin{center}
\includegraphics[scale=0.50]{flips.gif}
\end{center}

\section{Results}
Our algorithm to remove edges from a Delaunay Triangulation showed a reduction in weight from 1110.45 to 1029.2. 
The below tables summarise the results of our experiments with other approaches.
\begin{table}[ht]
\caption{Weight of Triangulation}
\centering
% used for centering table
\begin{tabular}{c c c}
\hline\hline
Approach & Triangulation & After removing edges\\ [0.5ex]
\hline
Regular & 1487.22 & 1455.45 \\
Greedy  & 1908.7 & 1895.33 \\
Delaunay & 1110.45 & 1029.2\\[1ex]
\hline
\end{tabular}
\label{table:nonlin}
\end{table}

\begin{table}[ht]
\caption{Number Of Faces}
\centering
% used for centering table
\begin{tabular}{c c c}
\hline\hline
Approach & Triangulation & After removing edges\\ [0.5ex]
\hline
Regular & 4128 & 4038 \\
Greedy  & 3678 & 3648 \\
Delaunay & 7168 & 6614\\[1ex]
\hline
\end{tabular}
\label{table:nonlin}
\end{table}

One interesting fact we observed after running these experiments is that the Delaunay Triangulation generates more number of triangles, still gives a lesser weight than the others.

\end{document}          
